package ruijie;

import java.util.HashMap;
import java.util.Map;

public class Main4 {

    class RandomListNode {
        int label;
        RandomListNode next, random;

        RandomListNode(int x) {
            this.label = x;
        }
    }

    Map<RandomListNode,RandomListNode> map = new HashMap<>();

    public RandomListNode copyRandomList(RandomListNode head) {
        if(head == null) return null;

        if(!map.containsKey(head)){
            RandomListNode randomListNode = new RandomListNode(head.label);
            map.put(head,randomListNode);
            randomListNode.next = copyRandomList(head.next);
            randomListNode.random = copyRandomList(head.random);
        }

        return map.get(head);
    }
}
//        if(head == null) return null;
//
//        ArrayList<RandomListNode> list = new ArrayList<>();
//        ArrayList<RandomListNode> mylist = new ArrayList<>();
//
//        for(RandomListNode p = head;p!=null;p = p.next){
//            list.add(p);
//            mylist.add(new RandomListNode(p.label));
//        }
//
//        for(int i = 0;i<list.size()-1;i++){
//            mylist.get(i).next = mylist.get(i+1);
//        }
//        mylist.get(mylist.size()-1).next = null;
//
//        for(int i = 0;i<list.size();i++){
//            int index = list.indexOf(list.get(i).random);
//
//
//
//            if(index!=-1){
//                mylist.get(i).random = mylist.get(index);
//            }else {
//                mylist.get(i).random = null;
//            }
//        }
//
//        return mylist.get(0);